This invention relates generally to processor-based systems and, particularly, to systems that need to locate a most or least significant bit of a computer word.
In a number of circumstances, it is desirable to locate the most or least significant bit of a computer word. For example, in various arithmetic operations this may be desirable. In particular, it is useful to know where the most significant bit is located to estimate the quotient for division, as well as in a variety of other situations.
One technique to find a significant bit is to simply look at each bit in order and to stop when the first non-zero bit is found. While this approach is simple, it has a running time proportional to the length of the data.
Alternatively, the most significant bit may be located by treating the datum as an integer and performing a binary search for the least power of two which is greater than the datum. This result can then be used to directly compute the index of the most significant bit. Although this algorithm may reduce the computational complexity to the log of the datum size, the overhead for testing and branching is high.
Thus, there is a need for better ways to locate significant bits.